#include <stdio.h>

inline void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void siftdown(int *data, int pos, int end)
{
	int c;
	while (1) {
		c = (pos << 1) + 1;
		if (c > end)
			break;
		if (c + 1 <= end && data[c + 1] > data[c])
			c++;
		if (data[pos] > data[c])
			break;

		swap(data + pos, data + c);
		pos = c;
	}
}

void siftup(int *data, int pos)
{
	int p;
	while (1) {
		if (pos == 0)
			break;
		p = (pos - 1) >> 1;
		if (data[p] > data[pos])
			break;
		swap(data + p, data + pos);
		pos = p;
	}
}

void heap_sort(int *data, int len)
{
	int i;
	
	for (i = 1; i < len; i++)
		siftup(data, i);
	for (i = len - 1; i > 0; i--) {
		swap(data + i, data);
		siftdown(data, 0, i - 1);
	}
}

int main() 
{
	int data[] = {8, 5, 3, 2, 4, 7, 1, 9};
	int i, len;

	len = sizeof(data) / sizeof(int);
	heap_sort(data, len);

	for (i = 0; i < len; i++)
		printf("%d ", data[i]);

	printf("\n");

	return 0;
}

